1. Field
The disclosure relates generally to protecting graph databases and more specifically to detecting denial-of-service attacks on graph databases using stored patterns of graph queries that identify whether a graph query is a denial-of-service attack.
2. Description of the Related Art
A graph database is a database that uses graph structures for semantic queries with nodes, edges, and properties to represent and store data. Nodes in the graph database represent entities, such as, for example, people, businesses, accounts, or any other item you might want to keep track of. Properties are pertinent information that relate to nodes. Edges represent the relationships that connect nodes to nodes or nodes to properties. The edges may be directed from one node to another or undirected with no specific from-to relationship between a pair of nodes.
A graph database may be brought down via one or more graph queries that are computationally intensive and intractable. Such a graph query may belong to an NP-complete, NP-hard, or other such computational complexity class (See, for example, Garey et al., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., New York, N.Y. (1979)). Such an action to bring down a graph database using a graph query that is computationally intensive and intractable is referred to a denial-of-service (DoS) attack.
A denial-of-service attack is an attempt to make a machine or network resource unavailable or available with a very low level of service, such as an unacceptable amount of response time, by consuming its resources so that it can no longer provide its intended service. In this case, the denial-of-service attack is an effort to temporarily or indefinitely interrupt or suspend services provided by the graph database. A denial-of-service attack that is sent by two or more devices is referred to as a distributed denial-of-service attack (DDoS).